#include <iostream>
#include <vector>
#include <string>

using namespace std;

/*
二分法注意区间的定义
根据两种常见的区间定义，会有两种二分法的写法
*/

int search(vector<int> &nums, int target)
{
    int p = 0, q = nums.size() - 1, i;
    // 定义target在左闭右闭的区间
    while (p <= q)
    {
        i = (p + q) / 2;
        if (target > nums[i])
        {
            // 注意i本身需要跳过
            p = i + 1;
        }
        else if (target < nums[i])
        {
            // 注意i本身需要跳过
            q = i - 1;
        }
        else
        {
            return i;
        }
    }
    return -1;
}

int main()
{
    vector<int> nums = {-1, 0, 3, 5, 9, 12};
    int target = 9;
    cout << search(nums, target) << endl;
    return 0;
}
